package main.java.com.amanda.suafa;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;
import main.java.com.amanda.innovate.DepthFirstOrder;
import main.java.com.amanda.utils.Digraph;

import java.util.Scanner;

/**
 * bug存在
 * @author amanda
 * @Description 算法4.6 计算强连通分量的Kosaraju算法
 */
public class KosarajuSCC {
    private boolean[] marked;   // 已经访问过的顶点
    private int[] id;
    private int count;
    public KosarajuSCC(Digraph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        DepthFirstOrder order = new DepthFirstOrder(G.reverse());
        for (int s : order.reversePost())
            if (!marked[s]) {
                dfs(G, s);
                count++;
            }
    }

    private void dfs(Digraph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w);
    }
    public boolean stronglyConnected(int v, int w) {
        return id[v] == id[w];
    }
    public int id(int v) {
        return id[v];
    }
    public int count() {
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Digraph G = new Digraph(scanner);
        KosarajuSCC scc = new KosarajuSCC(G);

        int m = scc.count();
        StdOut.println(m + " strong components");

        Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
        for (int i = 0; i < m; i++) {
            components[i] = new Queue<Integer>();
        }
        for (int v = 0; v < G.V(); v++) {
            components[scc.id(v)].enqueue(v);
        }
        for (int i = 0; i < m; i++) {
            for (int v : components[i]) {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }
    }
}
/*
13 22
4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 7 9 10 12 11 4 4 3 3 5 6 8 8 6 5 4 0 5 6 4 6 9 7 6
*/